package com.offer;

/**
 * @program: study
 * @className: NQuene
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2019-12-20 12:02
 * @version: v1.0
 **/
public class NQueen {

    private int[] result = new int[8];

    public static void main(String[] args) {
        NQueen nQueen = new NQueen();
        nQueen.calNQueens(0);
    }

    /**
     * 功能描述: n皇后调用
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019/12/20 12:03 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019/12/20 12:03 下午
     **/
    public void calNQueens(int rows) {

        /**
         * 1. 到达边界条件退出
         */
        if (rows == 8) {
            print(result);
            return;
        }

        /**
         * 2. 判定子的位置
         * 每行中有8列，所以有把中放法
         */

        for (int column = 0; column < 8; ++column) {

            if (isOk(rows, column)) {
                result[rows] = column;
                //3. 下一行
                calNQueens(rows + 1);
            }

        }


    }

    private final void print(int[] results) {
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (result[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * 功能描述: 判断行列放置是否合适
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019/12/20 3:06 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019/12/20 3:06 下午
     **/
    private final boolean isOk(int row, int column) {

        /**
         * 对于一个点，该列、对角线是否已经存在棋子（对角线：每行针对该列的对角线）
         * 只需要判断上半部分就好了
         */

        int left = column - 1, right = column + 1;
        for (int i = row - 1; i >= 0; --i) {
            //注意：每行中的数组中存储是该行相应的列
            if (result[i] == column) {
                return false;
            }

            /**
             * 考察左上对角列
             */
            if (left >= 0) {
                if (result[i] == left) {
                    return false;
                }
            }

            if (right < 8) {
                if (result[i] == right) {
                    return false;
                }
            }
            --left;
            ++right;
        }
        return true;
    }
}
